3004. Queue

 

In civilized countries k ticket offices are working at the train station, but the queue to them is just one. The service works as follows. Initially, when all the ticket offices are free, the first k people from the queue go to the offices. The others are waiting their turn. As soon as someone is served and the corresponding office becomes free, the next person in the queue comes to this office. This continues until all the people will be served.

Find the time to serve all the clients.

 

Input. The first line contains two integers: the queue size n and the number of ticket offices k (1 ≤ n ≤ 105, 1 ≤ k ≤ 104). n positive integers are given in the second line. The i-th number gives the time ti (1 ≤ ti ≤ 105) to serve the i-th client in the queue.

 

Output. Print one integer – the time to serve all the people in the queue.

 

Sample input

Sample output

7 3

1 2 3 4 5 3 1

7

 

 

SOLUTION

set

 

Algorithm analysis

Lets simulate the process of selling tickets using the multiset s. Bring the first k people to free cash desks and store their service time in the multiset. During further processing, the multiset will contain k elements. Each value in multiset reflects the time moment when the corresponding cash register will become free and the next person will be able to approach it. Obviously, each time a new person must come to the cash register for which this time is minimal. The time of the last served client will be the desired one.

 

Example

Consider the sample given. Put k = 3 first elements to the heap.

 

Then, at each iteration, we take the next element (the next person from the queue) and put it instead of the smallest one (we put the person to the ticket office that will be released earlier). We put to the queue the time at which this new person leaves the ticket office. Next to each figure the numbers in the heap are given.

 

 

Algorithm realization

Store the information about the points in time when tickets are sold at the office in the multiset s.

 

multiset<long long> s;

 

Read the input data. The service time of the first k people is saved in the multiset s.

 

scanf("%d %d",&n,&k);

for(i = 0; i < n; i++)

{

  scanf("%d",&ti);

  if (s.size() != k) s.insert(ti);

  else

  {

 

Find the person who leaves the ticket office first and put the next person from the queue behind him.

 

    long long temp = *s.begin();

    s.erase(s.begin());

    s.insert(temp + ti);

  }

}

 

The largest number in the multiset s equals to the time when the last client will be served. It will be the answer.

 

while(s.size() > 1) s.erase(s.begin());

printf("%lld\n",*s.begin());

 

Algorithm realization – priority queue

Create a heap, which root contains the smallest element.

 

priority_queue<long long, vector<long long>, greater<long long> > pq;

 

Read the input data. Put the service time of the first k people into the queue pq.

 

scanf("%d %d",&n,&k);

for(i = 0; i < n; i++)

{

  scanf("%d",&ti);

  if (pq.size() != k) pq.push(ti);

  else

  {

 

Find the person who leaves the ticket office first and put the next person from the queue behind him.

 

    long long temp = pq.top(); pq.pop();

    pq.push(temp + ti);

  }

}

 

The largest number in queue pq equals to the time when the last client will be served. It will be the answer.

 

while(pq.size() > 1) pq.pop();

printf("%lld\n",pq.top());

 

Java realization

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int k = con.nextInt();

    PriorityQueue<Long> pq = new PriorityQueue<Long>();

    for(int i = 0; i < n; i++)

    {

      long ti = con.nextLong();

      if (pq.size() != k) pq.add(ti);

      else pq.add(pq.poll() + ti);

    }

    while(pq.size() > 1) pq.poll();

    System.out.println(pq.poll());

   }

}